package q239;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

/**
 * 239. 滑动窗口最大值
 */
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] slidingWind = new int[nums.length - k + 1];
        slidingWind[0] = Integer.MIN_VALUE;
        int maxIdx = 0;
        for (int i = 0; i < k; i++) {
           if (nums[i] > slidingWind[0]) {
               slidingWind[0] = nums[i];
               maxIdx = i;
           }
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] >= slidingWind[i - k] || i <= maxIdx) {
                slidingWind[i - k + 1] = nums[i];
            } else {
                int max = Integer.MIN_VALUE;
                for (int j = 0; j < k; j++) {
                    if (nums[i - j] > max) {
                        max = nums[i - j];
                        maxIdx = i - j;
                    }
                }
                slidingWind[i - k + 1] = max;
            }
        }

        return slidingWind;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (k == 1) return nums;
        int[] slidingWind = new int[nums.length - k + 1];
        // 记录经历的波峰
        LinkedList<Integer> crestList = new LinkedList<>();

        // 波峰最大值
        int crestMax = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {

            if (i > 1 && nums[i - 2] <= nums[i - 1] && nums[i - 1] >= nums[i] && k >= 3) {
                // 波峰
                crestList.add(i - 1);
                crestMax = Math.max(crestMax, nums[i - 1]);
            }

            if (nums[i] >= crestMax) {
                crestMax = nums[i];
                crestList.clear();
            }

            if (!crestList.isEmpty() && crestList.get(0) == i - k) {
                // 移除已经走过的
                Integer remove = crestList.remove(0);

                // 重新寻找波峰最大值
                if (crestMax == nums[remove]) {
                    crestMax = Integer.MIN_VALUE;
                    for (int j = 0; j < crestList.size(); j++) {
                        crestMax = Math.max(nums[crestList.get(j)], crestMax);
                    }
                }
            }

            if (i >= k - 1) {
                slidingWind[i - k + 1] = Math.max(Math.max(nums[i], crestMax), nums[i - k + 1]);
            }
        }


        return slidingWind;
    }

    public int[] maxSlidingWindow3(int[] nums, int k) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1] == 0 ? o2[0] - o1[0] : o2[1] - o1[1]);

        for (int i = 0; i < k; i++) {
            priorityQueue.offer(new int[]{i, nums[i]});
        }

        int[] sliding = new int[nums.length - k + 1];
        sliding[0] = priorityQueue.peek()[1];

        for (int i = k; i < nums.length; i++) {
            while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] <= i - k) {
                priorityQueue.poll();
            }
            if (priorityQueue.peek() != null && nums[i] >= priorityQueue.peek()[1]) priorityQueue.clear();
            priorityQueue.offer(new int[]{i, nums[i]});
            sliding[i - k + 1] = priorityQueue.peek()[1];
        }

        return sliding;
    }

    public static void main(String[] args) throws IOException {
//        int[] nums = {3,3,-1,-1,5,3,6,7};
//        int k = 3;

//        int[] nums = {1};
//        int k = 1;

//        int[] nums = {9,10,9,-7,-4,-8,2,-6};
//        int k = 5;

//        int[] nums = {-6,-10,-7,-1,-9,9,-8,-4,10,-5,2,9,0,-7,7,4,-2,-10,8,7};
//        int k = 7;

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(Solution.class.getClassLoader().getResourceAsStream("q239\\Solution.txt")));
        String line = bufferedReader.readLine();
        List<Integer> list = Arrays.stream(line.split(",")).map(Integer::parseInt).collect(Collectors.toList());
        int[] nums = new int[list.size()];
        for (int i = 0; i <  nums.length; i++) {
            nums[i] = list.get(i);
        }
        int k = 50000;

        Solution solution = new Solution();
        int[] ints = solution.maxSlidingWindow3(nums, k);
        System.out.println(ints);
    }
}
